package myself.a015Dp;


/**
 * @author 叶之越
 * Description
 * Date 2021/2/2
 * Time 14:11
 * Mail 739153436@qq.com
 */
public class ConvertToLetterString {
    // 字符串转换

    // 暴力递归
    public static int number(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        return process(str.toCharArray(), 0);
    }

    // str[0..i-1]转化无需过问
    // str[i.....]去转化，返回有多少种转化方法
    public static int process(char[] str, int i) {
        if (i == str.length) {
            return 1;
        }
        if (str[i] == '0') {
            return 0;
        }
        // 当前字符进行拼接
        int ways = process(str, i + 1);

        // 当前连续两个字符进行拼接
        if (i + 1 < str.length && (str[i] - '0') * 10 + (str[i + 1] - '0') <= 26) {
            ways += process(str, i + 2);
        }
        return ways;
    }

    // dp分析

    public static int dp(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int N = s.length();
        char[] chars = s.toCharArray();

        int[] cache = new int[N + 1];
        cache[N] = 1;
        for (int i = N - 1; i >= 0; i--) {
            if (chars[i] != '0') {
                // 当前字符进行拼接
                int ways = cache[i];

                // 当前连续两个字符进行拼接
                if (i + 1 < chars.length && (chars[i] - '0') * 10 + (chars[i + 1] - '0') <= 26) {
                    ways += cache[i + 2];
                }
                cache[i] = ways;
            }
        }
        return cache[0];
    }
}
